package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode77 {

    List<List<Integer>> result = new ArrayList<>();

    //使用回溯/递归
    public List<List<Integer>> combine(int n, int k) {
        calculation(n, k, 0, new ArrayList<>());
        return result;
    }

    private void calculation(int n, int count, int lastIndex, List<Integer> lastResult) {
        if (count == 0) {
            result.add(lastResult);
            return;
        }
        for (int i = lastIndex + 1; i <= n; i++) {
            List<Integer> list = new ArrayList<>(lastResult);
            list.add(i);
            calculation(n, count - 1, i, list);
            list.remove(list.size() - 1);
        }
    }

    //------------------------------------------------------------------
    List<List<Integer>> output = new LinkedList();
    int n;
    int k;

    public void backtrack(int first, LinkedList<Integer> curr) {
        // if the combination is done
        if (curr.size() == k)
            output.add(new LinkedList(curr));//重新包装结果

        for (int i = first; i < n + 1; ++i) {
            // add i into the current combination
            curr.add(i);
            // use next integers to complete the combination
            //移除当前结果，重新计算
            backtrack(i + 1, curr);
            // backtrack
            curr.removeLast();
        }
    }
}
